package com.demo.algorithms.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 计数排序：时间复杂度为Ο(n+k)
 * 计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。
 * 它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），
 * 快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，
 * 而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序
 * （基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）
 * <p>
 * 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
 * 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
 * <p>
 * 计数排序对输入的数据有附加的限制条件：
 * 1.输入的线性表的元素属于有限偏序集S；
 * 2.设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。
 * 在这两个条件下，计数排序的复杂性为O(n)。
 *
 * @author: 蔡奇峰
 * @date: 2020/7/29 下午5:03
 */
public class CountSort {
    public static void main(String[] args) {
        int[] arr = {6, 2,  8, 1};
//        int[] arr = {6, 2, 5, 2, 8, 66, 22, 17, 18, 1, 88, 98, 168, 178};

        /*int[] arr = new int[67780];
        for (int i = 0; i < 67780; i++) {

            arr[i] = new Random().nextInt(18060);
        }*/
        System.out.println("数组排序前：" + Arrays.toString(arr));

        long timeMillis = System.currentTimeMillis();
        int[] result = sort(arr);
        long timeMilli = System.currentTimeMillis();

        System.out.println("计数排序耗时：" + (timeMilli - timeMillis));
        System.out.println("数组排序后：" + Arrays.toString(result));
    }

    /**
     * 计数排序
     *
     * @param arr 要排序的数组（从小到大）
     */
    public static int[] sort(int[] arr) {
        // 创建
        int[] newArr = new int[arr.length];

        int max = arr[0], min = arr[0];
        // 遍历数组得到最大值和最小值
        for (int i : arr) {
            if (max < i) {
                max = i;
            }
            if (min > i) {
                min = i;
            }
            // max = max > i ? max : i;
            // min = min < i ? min : i;
        }
        // max - min 得到极差值
        int k = max - min;
        // 这个count数组的长度一般都比 arr长
        int[] count = new int[k + 1];

        // 通过arr[i] - min 可以得到排序的数组, arr[i]值越小越在count数组前面
        for (int i = 0; i < arr.length; i++) {
            // count的值加1且必须为1,否则newArr数组下标越界, 后面取值时需要减掉1得到原来的值
            count[arr[i] - min] += 1;
            // ++count[arr[i] - min];
        }

        // 可以根据得到的count数组得到原来arr数组的排序顺序
        for (int i = 1; i < count.length; ++i) {
            // 累加
            count[i] = count[i] + count[i - 1];
        }
        //
        for (int i = arr.length - 1; i >= 0; --i) {
            // arr[i] - min得到在count数组的下标, count的值减1 得到原来的值
//            int index = count[arr[i] - min] -1;
            // count的值减1 得到原来的值
//            newArr[index] = arr[i];
            newArr[--count[arr[i] - min]] = arr[i];
        }

        return newArr;
    }
}
